package LinkedList;

import Utils.ListNode;

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * Lettcode 24: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 */
public class swapPairs {
    /**
     * 方法一：递归
     * 只考虑第一步和下一步
     * 第一步： 反转第一个节点start和第二个节点end，反转过后，第一个节点变为end,第二个节点变为start
     * 第二步： 将第二个节点start.next = swapPairs(原来的end.next); 此时链表反转成功
     * @param head 需要被反转的链表头
     * @return 两两反转之后的链表
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode start = head;
        ListNode end = head.next;
        ListNode temp = swapPairs(end.next);
        start.next = temp;
        end.next = start;
        return end;
    }

    /**
     * 用两个指针遍历整个链表
     * @param head
     * @return
     */
    public ListNode swapPairsI(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode prevNode = dummyNode;

        while ((head != null) && (head.next != null)) {
            ListNode firstNode = head;
            ListNode secondNode = head.next;
            prevNode.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;

            prevNode = firstNode;
            head = firstNode.next;
        }
        return dummyNode.next;
    }
}
